﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;
template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	T _data;
	int _bf;   // 节点的平衡因子
};


// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	AVLTree()
		: _pRoot(nullptr)
	{}

	Node* Find(const T& key) {
		Node* cur_root = _pRoot;
		while (cur_root) {
			if (key > cur_root->_data) {
				cur_root = cur_root->_pRight;
			}
			else if (key == cur_root->_data) {
				return cur_root;
			}
			else {
				cur_root = cur_root->_pLeft;
			}
		}
		return nullptr;
	}

	// 在AVL树中插入值为data的节点
	bool Insert(const T& data) {
		//搜索树插入
		Node* cur_root = _pRoot;
		Node* parent_cur_root = nullptr;
		while (cur_root != nullptr) {
			parent_cur_root = cur_root;
			if (cur_root->_data == data) return false;
			if (cur_root->_data > data) cur_root = cur_root->_pLeft;
			else cur_root = cur_root->_pRight;
		}
		Node* new_root = new Node();
		new_root->_data = data;
		new_root->_bf = 0;
		new_root->_pParent = parent_cur_root;
		if (!parent_cur_root) { _pRoot = new_root; return true; }//当根为空节点时
		if (data > parent_cur_root->_data) { parent_cur_root->_pRight = new_root; parent_cur_root->_bf++; }
		else {
			parent_cur_root->_pLeft = new_root; parent_cur_root->_bf--;
		}
		//更新平衡因子

		cur_root = parent_cur_root;
		while (cur_root->_bf != 0) {
			if (!cur_root) return true;
			if (!cur_root->_pParent) return true;//到达了根节点退出
			if (cur_root->_pParent->_data > cur_root->_data) {
				cur_root->_pParent->_bf--;
				if (fabs(cur_root->_pParent->_bf)>=2) {
					assert(cur_root->_pParent->_bf == -2);
					if (cur_root->_bf < 0){//右单旋cur_root->_pParent->_bf的值为-2由于--
						RotateR(cur_root->_pParent);
						return true;
					}
					else {//先左单旋转，再右单旋，的双旋
						RotateLR(cur_root->_pParent);
						return true;
					}
				}
			}
			else {
				cur_root->_pParent->_bf++;
				if (fabs(cur_root->_pParent->_bf) >= 2) {
					assert(cur_root->_pParent->_bf == 2);
					if (cur_root->_bf > 0) {//左单旋cur_root->_pParent->_bf的值为2由于++
						RotateL(cur_root->_pParent);
						return true;
					}
					else {//先右单旋转，再左单旋，的双旋
						RotateRL (cur_root->_pParent);
						return true;
					}
				}
			}
			cur_root = cur_root->_pParent;
		}



		return true;
	}

	void InOrder()
	{
		_InOrder(_pRoot);
		cout << endl;
	}
	int Height() {
		return _Height(_pRoot);
	}

	// AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot);
	}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_pLeft);
		cout << root->_data << ":" << root->_data << endl;
		_InOrder(root->_pRight);
	}


	bool _IsBalanceTree(Node* root)
	{
		// 空树也是AVL树
		if (nullptr == root)
			return true;
		// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差
		int leftHeight = _Height(root->_pLeft);
		int rightHeight = _Height(root->_pRight);
		int diff = rightHeight - leftHeight;
		// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者
		// pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树
		if (abs(diff) >= 2)
		{
			cout << root->_data << "高度差异常" << endl;
			return false;
		}
		if (root->_bf != diff)
		{
			cout << root->_data << "平衡因⼦异常" << endl;
			return false;
		}
		// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树
		return _IsBalanceTree(root->_pLeft) && _IsBalanceTree(root->_pRight);
	}
	// 根据AVL树的概念验证pRoot是否为有效的AVL树
	bool _IsAVLTree(Node* pRoot) {
		return _IsBalanceTree(pRoot);
		
	}
	size_t _Height(Node* pRoot) {
		if (pRoot == nullptr) return 0;
		int leftsize = _Height(pRoot->_pLeft);
		int rightsize = _Height(pRoot->_pRight);
		return leftsize > rightsize ? leftsize + 1 : rightsize + 1;
	}
	// 右单旋
	void RotateR(Node* pParent) {
		Node* subl = pParent->_pLeft;
		Node* sublr = subl->_pRight;
		subl->_pRight = pParent;
		if (pParent->_pParent) {//判断根节点
			subl->_pParent = pParent->_pParent;
			if (pParent->_pParent->_data > pParent->_data) {
				pParent->_pParent->_pLeft = subl;
			}
			else pParent->_pParent->_pRight = subl;
		}
		else {
			subl->_pParent = nullptr;
			_pRoot = subl;
		}
		
		if(sublr) sublr->_pParent = pParent;
		pParent->_pParent = subl;
		subl->_pRight = pParent;
		pParent->_pLeft = sublr;

		
		
		//更新平衡因子
		subl->_bf = 0;
		pParent->_bf = 0;
	}
	// 左单旋
	void RotateL(Node* pParent) {
		Node* subr = pParent->_pRight;
		Node* subrl = subr->_pLeft;
		subr->_pLeft = pParent;
		if (pParent->_pParent) {//判断根节点
			subr->_pParent = pParent->_pParent;
			if (pParent->_pParent->_data > pParent->_data) {
				pParent->_pParent->_pLeft = subr;
			}
			else pParent->_pParent->_pRight = subr;
		}
		else {
			subr->_pParent = nullptr;
			_pRoot = subr;
		}

		if (subrl) {
			subrl->_pParent = pParent;
		}
		pParent->_pParent = subr;
		subr->_pLeft = pParent;
		pParent->_pRight = subrl;
		//更新平衡因子
		subr->_bf = 0;
		pParent->_bf = 0;
		
	}
	// 右左双旋
	void RotateRL(Node* pParent) {
		Node* subr = pParent->_pRight;
		Node* subrl = subr->_pLeft;
		if (subrl->_bf == 0) {
			RotateR(subr);
			RotateL(pParent);
			subr->_bf = pParent->_bf = subrl->_bf = 0;
		}
		else if (subrl->_bf == 1) {
			RotateR(subr);
			RotateL(pParent);
			pParent->_bf = -1;
			subr->_bf = subrl->_bf = 0;
		}
		else if (subrl->_bf == -1) {
			RotateR(subr);
			RotateL(pParent);
			subr->_bf = 1;
			subrl->_bf = pParent->_bf = 0;
		}
	}
	// 左右双旋
	void RotateLR(Node* pParent) {
		Node* subl = pParent->_pLeft;
		Node* sublr = pParent->_pLeft->_pRight;
		if (sublr->_bf == 0) {
			RotateL(subl);
			RotateR(pParent);
			subl->_bf = pParent->_bf = sublr->_bf = 0;
		}
		else if (sublr->_bf == 1) {
			RotateL(subl);
			RotateR(pParent);
			subl->_bf = -1;
			sublr->_bf = pParent->_bf = 0;
		}
		else if (sublr->_bf == -1) {
			RotateL(subl);
			RotateR(pParent);
			pParent->_bf = 1;
			subl->_bf = sublr->_bf = 0;
		}
	}

private:
	Node* _pRoot;
};
// 测试代码
void TestAVLTree1()
{
	AVLTree<int> t;
	// 常规的测试⽤例
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的带有双旋场景的测试⽤例
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();
	cout << t.IsAVLTree() << endl;
}
// 插⼊⼀堆随机值，测试平衡，顺便测试⼀下⾼度和性能等
void TestAVLTree2()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
		size_t begin2 = clock();
	AVLTree<int> t;
	for (auto e : v)
	{
		t.Insert(e);
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsAVLTree() << endl;
	cout << "Height:" << t.Height() << endl;
	//cout << "Size:" << t.Size() << endl;
	size_t begin1 = clock();
	// 确定在的值
	/*for (auto e : v)
	{
	t.Find(e);
	}*/
	// 随机值
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}

int main() {
	TestAVLTree2();
	TestAVLTree1();
}









